package com.copa.l102;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-05-19 14:56
 * @function BFS（广度优先遍历）
 */
public class Test2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (Objects.isNull(root)) {
            // 题目中有可能为空，所以这里处理先返回空
            return result;
        }
        // 这里定义队列，方便遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 先添加根节点
        queue.add(root);
        // 如果此时队列长度不为0，则需要遍历
        while (queue.size() > 0) {
            // 开始一层遍历
            List<Integer> tempList = new ArrayList<>();
            int length = queue.size();
            while (length > 0) {
                // 这一层节点的逐个遍历
                TreeNode temp = queue.poll();
                if (temp.left != null) {
                    // 若该节点的左子树有值，则添加该节点的左子树到队列中
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    // 若该节点的右子树有值，则添加该节点的右子树到队列中
                    queue.add(temp.right);
                }
                tempList.add(temp.val);
                length--;
            }
            result.add(tempList);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        TreeNode root = new TreeNode(3, left, right);
        List<List<Integer>> result = new Test2().levelOrder(root);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
